/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package collections.utils;

import collections.exceptions.MyIndexOutOfBoundsException;
import collections.exceptions.MyNoComparatorException;
import collections.list.MyArrayList;
import collections.list.MyLinkedList;
import collections.list.interfaces.MyList;
import collections.list.interfaces.RandomAccess;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;

/**
 *
 * @author Iaroslav_Mazai
 */
public class MyCollections {

	private static class DefaultComparator implements Comparator<Object> {

		@Override
		public int compare(Object o1, Object o2) {
			Comparable c1 = (Comparable) o1;
			Comparable c2 = (Comparable) o2;

			if (c1 == null) {
				return -1;
			}
			if (c2 == null) {
				return 1;
			}

			return c1.compareTo(o2);
		}
	}

	private static void checkIndex(MyList list, int index) {
		if (list.size() <= index) {
			throw new MyIndexOutOfBoundsException();
		}
	}

	private static void randomAccessSort(MyList list, Comparator c) {
		Object[] array = list.toArray();
		array = quickSort(array, c);
		list.clear();
		list.addAll(array);
	}

	private static Object[] quickSort(Object[] data, Comparator c) {
		int size = data.length;
		if (size <= 1) {
			return data;
		}

		int pivotIndex = size / 2;
		Object pivot = data[pivotIndex];

		Object[] less = new Object[size];
		Object[] greater = new Object[size];

		int lessSize = 0;
		int greaterSize = 0;
		for (int i = 0; i < size; i++) {
			if (c.compare(data[i], pivot) < 0) {
				less[lessSize] = data[i];
				lessSize++;
			} else {
				if (i != pivotIndex) {
					greater[greaterSize] = data[i];
					greaterSize++;
				}
			}
		}

		Object[] sortedLess = new Object[lessSize];
		Object[] sortedGreater = new Object[greaterSize];
		System.arraycopy(less, 0, sortedLess, 0, lessSize);
		System.arraycopy(greater, 0, sortedGreater, 0, greaterSize);

		sortedLess = quickSort(sortedLess, c);
		sortedGreater = quickSort(sortedGreater, c);

		Object[] result = new Object[size];

		for (int i = 0; i < lessSize; i++) {
			result[i] = sortedLess[i];
		}

		result[lessSize] = pivot;

		for (int i = 0; i < greaterSize; i++) {
			result[lessSize + i + 1] = sortedGreater[i];
		}

		return result;
	}

	private static void sequentialAccessSort(MyList list, Comparator c) {
		Object[] data = list.toArray();
		bubbleSort(data, c);
		list.clear();
		list.addAll(data);
	}

	private static void bubbleSort(Object[] data, Comparator c) {
		int size = data.length;
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < i; j++) {
				if (c.compare(data[i], data[j]) < 0) {
					Object tmp = data[i];
					data[i] = data[j];
					data[j] = tmp;
				}
			}
		}
	}

	public static void sort(MyList list) {
		if (list.isEmpty()) {
			return;
		}
		if (list.get(0) instanceof Comparable) {
			sort(list, new DefaultComparator());
		} else {
			throw new MyNoComparatorException();
		}
	}

	public static void sort(MyList list, Comparator c) {
		if (list instanceof RandomAccess) {
			randomAccessSort(list, c);
		} else {
			sequentialAccessSort(list, c);
		}
	}

	public static void swap(MyList list, int i, int j) {
		checkIndex(list, i);
		checkIndex(list, j);
		Object tmp = list.get(i);
		list.set(i, list.get(j));
		list.set(j, tmp);
	}

	private static void randomAccessCopy(MyList dest, MyList src) {
		Iterator srcIterator = src.iterator();
		int i = 0;
		while (srcIterator.hasNext()) {
			Object value = srcIterator.next();
			dest.set(i, value);
			i++;
		}
	}

	private static void sequentialAccessCopy(MyList dest, MyList src) {
		int srcSize = src.size();
		int destSize = dest.size();

		Object[] destArray = dest.toArray();
		Object[] srcArray = src.toArray();

		System.arraycopy(srcArray, 0, destArray, 0, srcSize);

		dest.clear();
		dest.addAll(destArray);
	}

	public static void copy(MyList dest, MyList src) {
		if (dest.size() < src.size()) {
			throw new MyIndexOutOfBoundsException();
		}

		if (dest instanceof RandomAccess && src instanceof RandomAccess) {
			randomAccessCopy(dest, src);
		} else {
			sequentialAccessCopy(dest, src);
		}
	}

	private static void randomAccessReverse(MyList list) {
		int size = list.size();
		int pivot = size / 2;
		for (int i = 0; i < pivot; i++) {
			int src = i;
			int dst = size - i - 1;
			swap(list, src, dst);
		}
	}

	private static void sequentialAccessReverse(MyList list) {
		Object[] array = list.toArray();
		arrayReverse(array);
		list.clear();
		list.addAll(array);
	}

	private static void arrayReverse(Object[] array) {
		int size = array.length;
		int pivot = size / 2;
		for (int i = 0; i < pivot; i++) {
			int src = i;
			int dst = size - i - 1;
			arraySwap(array, src, dst);
		}
	}

	private static void arraySwap(Object[] array, int i, int j) {
		Object tmp = array[i];
		array[i] = array[j];
		array[j] = tmp;
	}

	public static void reverse(MyList list) {
		if (list instanceof RandomAccess) {
			randomAccessReverse(list);
		} else {
			sequentialAccessReverse(list);
		}
	}

	public static int binarySearch(RandomAccess list, Object key) {
		return binarySearch(list, key, 0, list.size());
	}
	
	private static int binarySearch(RandomAccess list, Object key, int from, int to){
		int length = to - from;
		if (length == 1){
			return -to -1;
		}
		int mid = from + (length / 2);
		Object midElement = list.get(mid);
		
		if (key.equals(midElement)){
			return mid;
		}
		if (((Comparable)key).compareTo(list.get(mid)) < 0){
			return binarySearch(list, key, from, mid);
		} else{
			return binarySearch(list, key, mid, to);
		}
	}
}
